<!DOCTYPE html>
<html lang="zh">
<head>
    <meta charset="UTF-8">
    <title>哈希表的实现</title>
</head>
<body>
<script>
        //封装哈希表
        function HashTable() {
            //属性
            this.storage = [];
            this.count = 0;
            this.limit = 7;

            //方法
            HashTable.prototype.hashFunc = function (str, size) {
                //定义hashcode变量
                var hashCode = 0;

                //计算hashCode变量
                for (let i = 0; i < str.length; i++) {
                    hashCode = hashCode * 37 + str.charCodeAt(i);
                }

                //取余操作
                var index = hashCode % size;
                return index;
            }

            //插入和修改方法
            /*
                    链地址法来解决冲突
            * */
            HashTable.prototype.put = function (key, value) {
                //1.根据key获取索引index
                var index = this.hashFunc(key,this.limit);
                //2.根据index取出对应的‘桶’
                var bucket = this.storage[index];

                //3.创建桶
                if (bucket == null){
                    bucket = [];
                    this.storage[index] = bucket;
                }

                //4.判断是否是修改数据
                for (let i = 0; i < bucket.length; i++) {
                    var tuple = bucket[i];
                    if (tuple[0] === key){
                        tuple[1] = value;
                        return;
                    }
                }

                //5.进行添加操作
                bucket.push([key,value]);
                this.count += 1;

                //判断是否需要扩容
                if (this.count > this.limit*0.75){
                    var newSize = this.limit*2;
                    var newPrime = this.getPrime(newSize);
                    this.resize(newPrime);
                }
            }

            //获取操作
            HashTable.prototype.get = function (key) {
                //1.根据key获取索引
                var index = this.hashFunc(key,this.limit);

                //2.根据索引获取 bucket
                var bucket = this.storage[index];
                //3.判断桶是否为空
                if (bucket == null){
                    return null;
                }else {
                    //线性查找
                    for (let i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key){
                            return tuple[1];
                        }
                    }
                    return null;
                }
            }

            //删除操作
            HashTable.prototype.remove = function (key) {
                //1.根据key获取index
                var index = this.hashFunc(key,this.limit);
                //2.根据key获取bucket
                var bucket = this.storage[index];
                //3.判断bucket是否为空
                if (bucket == null){
                    return null;
                }else {
                    //4.不为空 遍历bucket
                    for (let i = 0; i < bucket.length; i++) {
                        var tuple = bucket[i];
                        if (tuple[0] === key){
                            bucket.splice(i,1);
                            //歧义
                            this.count--;
                            return tuple[1];

                            //缩小容量
                            if (this.limit > 7 && this.count < this.limit*0.25){
                                var newSize = Math.floor(this.limit / 2);
                                var newPrime = this.getPrime(newSize);
                                this.resize(newPrime);
                            }
                        }
                    }
                    //5.遍历完成后依然没有找到
                    return null;
                }
            }
            //判断哈希表是否为空
            HashTable.prototype.isEmpty = function () {
                // return this.storage.length == null;
                return this.count == 0;
            }
            //获取哈希表里面元素的个数
            HashTable.prototype.size = function () {
                return this.count;
            }

            //哈希表的扩容
            HashTable.prototype.resize = function (newLimit) {
                //1.保存原来的数组
                var oldStorage = this.storage;
                //2.重置属性
                this.storage = [];
                this.count = 0;
                this.limit = newLimit;
                //3.遍历oldStorage
                for (let i = 0; i < oldStorage.length; i++) {
                    var bucket = oldStorage[i];
                    //判断桶是否为空
                    if (bucket == null){
                        continue;
                    }else {
                        for (let j = 0; j < bucket.length; j++) {
                            var tuple = bucket[j];
                            //重新插入
                            this.put(tuple[0],tuple[1]);
                        }
                    }
                }

            }

            //判断一个数是否是质数
            HashTable.prototype.isPrime = function (num) {

                var temp = parseInt(Math.sqrt(num));

                for (let i = 2; i <= temp; i++) {
                    if (num % i === 0){
                        return false;
                    }
                }
                return true;
            }

            //获取质数的方法
            HashTable.prototype.getPrime = function (num) {
                while(!this.isPrime(num)){
                    num++;
                }
                return num;
            }

        }


        //测试
        var ht = new HashTable();
        //插入
        ht.put('abc','123');
        ht.put('bcd','234');
        ht.put('bcd','234');
        ht.put('b','234');
        ht.put('bc','234');
        ht.put('ba','234');
        ht.put('d','234');
        ht.put('cd','234');
        ht.put('ca','234');
        ht.put('sd','234');

        //获取
        alert(ht.get('abc'));
        //修改
        ht.put('abc','777');
        //获取修改后的数据
        alert(ht.get('abc'));
        //删除
        ht.remove('abc');
        alert(ht.get('abc'));
        //获取长度
        alert(ht.size());
        //判断是否为空
        alert(ht.isEmpty());



</script>
</body>
</html>